1. Field of the Invention
The present invention relates to techniques for efficiently performing “belief-propagation” operations, which solve graphical inference problems through a series of local message-passing operations.
2. Related Art
Belief Propagation (BP) has recently established itself as an effective technique for solving some of the ill-posed labeling problems that are typical in computer vision. In these problems, each pixel becomes a node in a graph, and local information propagates by passing messages representing probability distributions along the edges to its neighbors. Messages are passed iteratively until convergence is reached.
Early applications of BP were to one-dimensional problems such as “contour matching.” (See Y. Weiss. Interpreting images by propagating Bayesian beliefs. In M. C. Mozer et al., editors, Advances in Neural Information Processing Systems 9, pages 908-915. Bradford Books, 1997.) These applications adhered to arguments that BP may not converge on graphs with loops (see J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988).
Later, BP was discovered to converge on a number of interesting problems involving loopy graphs and has since solved problems in tracking, image restoration, finding objects in clutter, and estimating occluded features, among others. Weiss and Freeman have provided a theoretical justification for the convergence of BP on such loopy graphs (see Y. Weiss and W. T. Freeman. Correctness of BP in Gaussian graphical models of arbitrary topology. Technical Report UCB/CSD-99-1046, UC-Berkeley, June 1999).
These promising results have spurred interest in speeding up BP. Felzenswalb and Huttenlocher discovered a number of useful optimizations to the BP algorithm itself, making it practical for a wider range of problems (see P. F. Felzenszwalb and D. P. Huttenlocher. Efficient belief propagation for early vision. In CVPR, volume I, pages 261-268, 2004).
Existing BP techniques perform a large number of computationally-expensive operations, such as multiplications. Iteratively performing these computationally-expensive operations during the BP process can consume a large amount of computational time. Hence, what is needed is a method and an apparatus for minimizing the number of computationally-expensive operations performed during the BP process.